package com.gitee.feizns.explore.data_structure.linked_list.singly.intersect;


/**
 * @author feizns
 * @since 2019/9/29
 */
public class Intersect {

    public static void main(String[] args) {
        ListNode[] nodes = create1();
        ListNode node = getIntersectionNode(nodes[0], nodes[1]);
        System.out.println(node);
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pointA = headA;
        ListNode pointB = headB;
        ListNode tailA = null;
        ListNode tailB = null;
        while ( pointA != pointB ) {
            if ( pointA.next == null ) {
                tailA = pointA;
                pointA = headB;
            } else
                pointA = pointA.next;

            if ( pointB.next == null ) {
                tailB = pointB;
                pointB = headA;
            } else
                pointB = pointB.next;

            if ( tailA != null && tailB != null && tailA != tailB )
                return null;
        }
        return pointA;
    }

//    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        Set<ListNode> nodes = getNodeSet(headB);
//        ListNode tmp = headA;
//        while ( tmp != null ) {
//            if ( nodes.contains(tmp) )
//                return tmp;
//            tmp = tmp.next;
//        }
//        return null;
//    }
//
//    private static Set<ListNode> getNodeSet(ListNode head) {
//        Set<ListNode> ret = new LinkedHashSet<>();
//        ListNode tmp = head;
//        while ( tmp != null ) {
//            ret.add(tmp);
//            tmp = tmp.next;
//        }
//        return ret;
//    }

    private static ListNode[] create1() {
        ListNode tmp1 = new ListNode(1);
        ListNode tmp2 = new ListNode(1);

        tmp1.next = new ListNode(2);
        tmp2.next = new ListNode(2);

        ListNode r = new ListNode(3);
//        tmp1.next = r;
//        tmp2.next = r;

        return new ListNode[]{ tmp1, tmp2 };
    }

}
